import collections
from typing import List


class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        size = len(rods)

        # 处理钢筋数量少于2根的情况
        if size < 2:
            return 0

        # 按长度倒序排序钢筋
        rods.sort(reverse=True)

        # 计算每个钢筋之后的钢筋总长度（后缀和）
        surplus = [0] * size
        surplus[-1] = rods[-1]
        for i in range(size - 2, -1, -1):
            surplus[i] = surplus[i + 1] + rods[i]

        # 计算单侧可能的极限最大高度
        max_height = sum(rods) // 2

        ans = 0

        dp1 = collections.defaultdict(int)
        dp1[0] = 0
        for i in range(size):
            dp2 = collections.defaultdict(int)
            rod = rods[i]

            for d1, v1 in dp1.items():
                # [剪枝1]剩余的钢筋已不足以支持当前情况超过当前最优解
                if v1 * 2 + d1 + surplus[i] <= ans * 2:
                    continue

                # [剪枝4]剩余的钢筋已不足以支持将两侧高度拉平
                if d1 > surplus[i]:
                    continue

                # 【选择1】不使用当前钢筋
                dp2[d1] = max(dp2[d1], v1)

                # 【选择2】将当前钢筋用到左侧
                # [剪枝2]避免左侧钢筋长度超过极限最大高度
                if v1 + d1 + rod <= max_height:
                    dp2[d1 + rod] = max(dp2[d1 + rod], v1)

                # 【选择3】将当前钢筋用到右侧
                # [剪枝3]避免右侧钢筋长度超过极限最大高度
                if v1 + rod <= max_height:
                    d2, v2 = abs(d1 - rod), v1 + min(d1, rod)
                    dp2[d2] = max(dp2[d2], v2)

            dp1 = dp2

        return dp1[0]


if __name__ == "__main__":
    print(Solution().tallestBillboard([1, 2, 3, 6]))  # 6
    print(Solution().tallestBillboard([1, 2, 3, 4, 5, 6]))  # 10
    print(Solution().tallestBillboard([1, 2]))  # 0
